public class code03s {
    public int findKthLargest(int[] nums, int k) {
        // 解法二：使用堆排序
        // 这里的思路是，首先建立一个大根堆，先将数据排列起来
        // 之后再在大根堆中寻找第 k 大的值

        int size = nums.length;
        createMaxHeap(nums, size);

        // 在完成大根堆的创建之后，尝试获取第 k 个最大值
        // 这里需要通过 for 循环重复 size - k 次的遍历，并且减少数组的长度，以此来将最大值浮现上来
        for(int i = nums.length - 1; i >= nums.length - k + 1; i--) {
            // 每次开始遍历前，现将当前最大的数移动到数组的尾部
            swap(nums, 0, i);
            // 在将最后一个位置上的元素进行删除操作
            size--;
            // 将调整后的数组重新进行大根堆的构建，将最大值移动到数组的第一个位置
            shiftDown(nums, 0, size);
        }

        // 第一个位置上就对应着最大值
        return nums[0];
    }

    // 实现创建大根堆
    public void createMaxHeap(int[] arr, int size) {
        // 大根堆的构建，这里需要将数组中的元素进行向下调整
        // 所以需要先获取到 父亲 节点
        for (int i = size / 2 - 1; i >= 0; i--) {
            // 将父节点传递到一个方法中，进行向下调整
            shiftDown(arr, i, size);
        }
    }

    public void shiftDown(int[] arr, int parent, int size) {
        // 定义两个指针，分别指向父亲节点的左右孩子
        int left = parent * 2 + 1;
        int right = parent * 2 + 2;

        // 还需要定义一个记录当前父亲节点的指针，判断交换操作
        int root = parent;

        // 先针对右子树进行判断
        if (right < size && arr[right] > arr[root]) {
            // 当由此的值大于 root 时，此时将根节点指针移动向 right 处
            // 以此来标记最大值
            root = right;
        }

        // 同理，针对左子树也这么判断
        if (left < size && arr[left] > arr[root]) {
            root = left;
        }

        // 当发现 root 节点被上面进行修改后，执行交换操作
        if (root != parent) {
            swap(arr, parent, root);

            // 在交换之后，以当前新的根节点在进行调整
            shiftDown(arr, root, size);
        }

    }

    public void swap(int[] arr, int parent, int root) {
        int tmp = arr[parent];
        arr[parent] = arr[root];
        arr[root] = tmp;
    }
}
